package com.mashibing.class12;

//在线测试链接 : letcode 333 https://leetcode.com/problems/largest-bst-subtree

/**
 * 找到了两颗子树都是搜索二叉树, 但是较大子树的有几个节点返回.
 * 满足搜索条件的搜索二叉树的子树的最大节点数的大小 等于该树的节点数的大小， 说明这棵树就是搜索二叉树.
 */
public class Code05_MaxSubBSTSize {
    // 提交时不要提交这个类
    public static class TreeNode {
        public int value;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int value) {
            this.value = value;
        }
    }

    public static class Info {
        public int maxBSTSubtreeSize; // 最大满足搜索条件最大子树的大小.
        public int allSize; // 整颗树的大小
        public int max;// 最大值
        public int min;// 最小值

        public Info(int maxBSTSubtreeSize, int allSize, int max, int min) {
            this.maxBSTSubtreeSize = maxBSTSubtreeSize;
            this.allSize = allSize;
            this.max = max;
            this.min = min;
        }
    }
    // 提交如下的代码，可以直接通过
    public static int largestBSTSubtree(TreeNode head) {
        if (head == null) {
            return 0;
        }
        return process(head).maxBSTSubtreeSize;
    }

    private static Info process(TreeNode treeNode) {
        if (treeNode==null){
            return null;
        }
        Info leftInfo = process(treeNode.left);
        Info rightInfo = process(treeNode.right);

        int allSize=0; // 整颗树的大小
        int max=0;// 最大值
        int min=0;// 最小值
        if (leftInfo!=null){
            max = Math.max(leftInfo.max,max);
            min = Math.min(leftInfo.min,min);
            allSize += leftInfo.allSize;
        }
        if (rightInfo!=null){
            max = Math.max(rightInfo.max,max);
            min = Math.min(rightInfo.min,min);
            allSize += rightInfo.allSize;
        }
        int p1 = -1;
        if (leftInfo!=null){
            p1 = leftInfo.maxBSTSubtreeSize;
        }
        int p2 = -1;
        if (rightInfo!=null){
            p2 = rightInfo.maxBSTSubtreeSize;
        }
        int p3 = -1;
        boolean leftBST = leftInfo==null?true:
                (leftInfo.maxBSTSubtreeSize == leftInfo.allSize);
        boolean rightBST = rightInfo==null?true:
                (rightInfo.maxBSTSubtreeSize == rightInfo.allSize);
        if (leftBST&&rightBST){
            boolean leftMaxLessX = leftInfo==null ? true : (leftInfo.max < treeNode.value);
            boolean rightMinMoreX = rightInfo==null ? true : (rightInfo.min > treeNode.value);
            if (leftMaxLessX&&rightMinMoreX){
                int leftSize = leftInfo==null? 0 : leftInfo.allSize;
                int rightSize = rightInfo==null?0: rightInfo.allSize;
                p3=leftSize+rightSize+1;
            }
        }
        int maxBSTSubtreeSize=Math.max(Math.max(p1,p2),p3); // 最大满足搜索条件最大子树的大小.
        return new Info(maxBSTSubtreeSize,allSize,max,min);
    }
}

/**
 * 总结 : 时间复杂度 都是 O(n).
 * 递归序.
 */
